/* 397. 整数替换 */
/**
 * @param {number} n
 * @return {number}
 */
/* 
    枚举所有的情况 
    当 n 为偶数时，我们唯一的方法将 n 替换成 n / 2
    当 n 为奇数时，我们可以选择将 n 增加 或减少 1 由于两种方法都会将 n 变成偶数
    那么下一步一定是除以2 因此我们可以看成是两次操作将 n 变成 (n + 1) / 2 或者 (n - 1) / 2
*/
var integerReplacement = function (n) {
	if (n === 1) return 0
	if (n % 2 === 0) return 1 + integerReplacement(Math.floor(n / 2))
	/* 
        细节:
        当 n == 2 ^ 31 - 1 时,计算 n + 1 会导致溢出，因此我们可以使用整数除法[n / 2] + 1 和
        [n / 2] 分别计算 (n + 1) / 2 或 (n - 1) / 2
    */
	return (
		2 +
		Math.min(
			integerReplacement(Math.floor(n / 2)),
			integerReplacement(Math.floor(n / 2) + 1)
		)
	)
}
/* 记忆化递归 */
const memo = new Map()
var integerReplacement = function (n) {
	if (n === 1) return 0
	if (!memo.has(n)) {
		if (n % 2 === 0) {
			memo.set(n, 1 + integerReplacement(Math.floor(n / 2)))
		} else {
			memo.set(
				n,
				2 +
					Math.min(
						integerReplacement(Math.floor(n / 2)),
						integerReplacement(Math.floor(n / 2) + 1)
					)
			)
		}
	}
	return memo.get(n)
}
/* 贪心 */
var integerReplacement = function (n) {
	let ans = 0
	while (n != 1) {
		if (n % 2 === 0) {
			++ans
			n = Math.floor(n / 2)
		} else if (n % 4 === 1) {
			ans += 2
			n = Math.floor(n / 2)
		} else {
			if (n === 3) {
				ans += 2
				n = 1
			} else {
				ans += 2
				n = Math.floor(n / 2) + 1
			}
		}
	}
	return ans
}
const ret = integerReplacement(1234)
console.log('integerReplacement :>>', ret)
